function numIslands(grid: string[][]): number {
  let m = grid.length
  let n = grid[0].length
  let num_islands = 0
  for (let r = 0; r < m; ++r) {
    for (let c = 0; c < n; ++c) {
      if (grid[r][c] == '1') {
        ++num_islands
        dfs(grid, r, c)
      }
    }
  }

  return num_islands

}

/**
 * 深搜
 */
function dfs(grid: string[][], r: number, c: number) {
  let m = grid.length
  let n = grid[0].length

  if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] == '0') {
    return
  }

  grid[r][c] = '0' // 访问过的陆地标记为 0
  dfs(grid, r - 1, c)
  dfs(grid, r + 1, c)
  dfs(grid, r, c - 1)
  dfs(grid, r, c + 1)
}

/**
 * 广搜
 */
function numIslands2(grid: string[][]): number {
  let m = grid.length
  let n = grid[0].length
  let num_islands = 0;

  for (let r = 0; r < m; ++r) {
    for (let c = 0; c < n; ++c) {
      if (grid[r][c] == '1') {
        ++num_islands
        grid[r][c] = '0'
        const neighbors = [[r, c]]
        while (neighbors.length) {
          let [row, col] = neighbors.pop() as [number,number]
          if (row - 1 >= 0 && grid[row - 1][col] == '1') {
            neighbors.push([row - 1, col])
            grid[row - 1][col] = '0'
          }
          if (row + 1 < m && grid[row + 1][col] == '1') {
            neighbors.push([row + 1, col])
            grid[row + 1][col] = '0'
          }
          if (col - 1 >= 0 && grid[row][col - 1] == '1') {
            neighbors.push([row, col - 1])
            grid[row][col - 1] = '0'
          }
          if (col + 1 < n && grid[row][col + 1] == '1') {
            neighbors.push([row, col + 1])
            grid[row][col + 1] = '0'
          }
        }
      }
    }
  }
  return num_islands
}
